package main

import (
	"fmt"
	"strconv"
)

//给你两个二进制字符串，返回它们的和（用二进制表示）。
//
// 输入为 非空 字符串且只包含数字 1 和 0。
//
//
//
// 示例 1:
//
// 输入: a = "11", b = "1"
//输出: "100"
//
// 示例 2:
//
// 输入: a = "1010", b = "1011"
//输出: "10101"
//
//
//
// 提示：
//
//
// 每个字符串仅由字符 '0' 或 '1' 组成。
// 1 <= a.length, b.length <= 10^4
// 字符串如果不是 "0" ，就都不含前导零。
//
// Related Topics 数学 字符串
// 👍 533 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
func addBinary(a string, b string) string {
	// 用数组实现. 分别把两个字符串翻转, 保存数组中, 如果不够位数, 则补全 0
	aLen := len(a)
	bLen := len(b)

	// 计算数组的最大长度
	maxLen := aLen
	if aLen < bLen {
		maxLen = bLen
	}

	// 初始化两个数组分别保存每个字符
	aArr := make([]int, maxLen)
	bArr := make([]int, maxLen)

	for i := aLen - 1; i >= 0; i-- {
		aArr[aLen-i-1] = int(a[i] - '0')
	}

	for i := bLen - 1; i >= 0; i-- {
		bArr[bLen-i-1] = int(b[i] - '0')
	}

	// 初始化结果数组
	rArr := make([]int, maxLen+1)
	carry := 0 // 记录进位
	for i :=0 ;i < maxLen;i++ {
		sum := aArr[i] + bArr[i] + carry
		carry = sum / 2
		sum = sum % 2
		rArr[i] = sum
	}

	if carry != 0 {
		rArr[maxLen] = carry
	} else {
		rArr  = rArr[0:maxLen]
	}

	// 对结果的数组拼接字符串
	rStr := ""
	for i:=len(rArr) - 1; i >= 0; i-- {
		rStr += strconv.Itoa(rArr[i])
	}

	return rStr
}
//leetcode submit region end(Prohibit modification and deletion)

func main() {
	a := "11"
	b := "1"

	c := "100"

	result := addBinary(a, b)
	fmt.Println(result)
	fmt.Println(c == result)
}
